package demo5;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-07-25
 * Time: 23:39
 */
public class Class_TrieTree {

    //创建前缀树节点

    public static class Node{

        public int pass ;//经过这节点的次数
        public int end;//以这个字符为结尾的次数

        public Node[] nexts ;//多叉树,每个节点都会有很多条路

        //构造方法

        public Node(){
            this.pass = 0;
            this.end = 0;
            this.nexts = new Node[26];//可能会有26条路
        }

    }

    //创建一颗前缀树

    public static class Trie{

        private Node root ;//前缀树的根节点

        public Trie(){
            root = new Node();//创建前缀树这个根节点
        }

        //insert方法---将字符串插入到这颗前缀树中

        public  void insert(String words){
            if(words == null){
                return ;
            }
            char[] str = words.toCharArray();//将字符串转化成字符数组

            Node node = root;
            node.pass++;//经过这个节点了
            int path = 0;
            for(int i =0 ;i<str.length;++i){
                path = str[i] - 'a';//该往path这条路走
                if(node.nexts[path] == null){
                    node.nexts[path] = new Node();//如果没有这条路就创建这条路
                }
                node = node.nexts[path];
                node.pass++;
            }
            node.end++;

        }

        //搜索这个单词words出现了几次
        public int search(String words){
             if(words == null) return 0;
             char[] str = words.toCharArray();

             Node node = root;
             int path = 0;
             for(int i =0;i<str.length;++i){
                 path = str[i] - 'a' ;//得到是哪条路

                 if(node.nexts[path]==null){
                      return 0;
                 }
                 node = node.nexts[path];
             }
             return node.end;
        }

        public int prefixNumber(String words){
            if(words == null){
                return 0;
            }
            char[] str = words.toCharArray();
            Node node = root;
            int path = 0;
            for(int i =0;i<str.length;++i){
                path = str[i] - 'a';
                if(node.nexts[path] == null){
                    return 0;
                }
                node = node.nexts[path];
            }
            return node.pass;
        }

        public void delete(String words){
            if(words == null) return ;

            if(search(words)!=0){

                char[] str = words.toCharArray();
                Node node = root;
                node.pass -- ;
                int path  = 0;
                for(int i = 0 ;i<str.length;++i){
                    path = str[i] - 'a';
                    if(--node.nexts[path].pass==0){
                        node.nexts[path] = null;
                    }
                    node = node.nexts[path];
                }
                node.end -- ;
            }
        }

    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("abghjc");
        trie.insert("abcd");
        trie.insert("abc");
        trie.insert("abfghjc");
        trie.delete("abc");
        System.out.println();
        System.out.println(trie.search("abc"));
    }


}
